/**
 * 给一个字符串包含 NWES ， 每个字母表示四个方向之一
 * 字符串表示从原点出发的一个移动序列
 * 给定K，要求将字符串最多修改K次，
 * 问修改后，移动过程中距离原点最大的曼哈顿距离是多少
 * 首先注意到曼哈顿距离两个坐标是互不影响的，可以单独为结果做贡献，因此我们只需要考虑N和S互换以及E和W互换即可，没有必要把NS改成EW。
 * 其次注意到一致性，即一遍修改中，不可能N和S同时变动，即要么改S为N，要么改N为S
 * 再次注意到无序性质，即如果需要改动一个S，则改前一个或者后一个对答案没有影响，因此我们可以直接修改最先碰到的需要修改的字母
 * 所以一共有4种可能的变化，即
 * (N->S,E->W)(N->S,W->E)(S->N,E->W)(S->N,W->E)
 * 挨个枚举一遍即可
 */

int f(int x, int y){
    if(x < 0) x = -x;
    if(y < 0) y = -y;
    return x + y;
}

class Solution {
public:
    int maxDistance(string s, int k) {
        int ans = proc(s, k, 'E', 'N');
        ans = max(ans, proc(s, k, 'E', 'S'));
        ans = max(ans, proc(s, k, 'W', 'S'));
        ans = max(ans, proc(s, k, 'W', 'N'));
        return ans;
    }

    int proc(string s, int k, char a, char b){
        int x = 0, y = 0;
        int ans = 0;
        for(auto c : s){
            if(k > 0){
                if(c == a) c ^= 'E' ^ 'W', --k;
                if(c == b) c ^= 'N' ^ 'S', --k;
            }
            switch(c){
                case 'E': x += 1; break;
                case 'S': y -= 1; break;
                case 'W': x -= 1; break;
                case 'N': y += 1; break;
            }
            ans = max(ans, f(x, y));
        }
        return ans;
    }
};